//给你两个字符串 word1 和 word2 。 
//
// 如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀 ，那么我们称字符串 x 是 合法的 。 
//
// 请你返回 word1 中 合法 子字符串 的数目。 
//
// 
//
// 示例 1： 
//
// 
// 输入：word1 = "bcca", word2 = "abc" 
// 
//
// 输出：1 
//
// 解释： 
//
// 唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。 
//
// 示例 2： 
//
// 
// 输入：word1 = "abcabc", word2 = "abc" 
// 
//
// 输出：10 
//
// 解释： 
//
// 除了长度为 1 和 2 的所有子字符串都是合法的。 
//
// 示例 3： 
//
// 
// 输入：word1 = "abcabc", word2 = "aaabc" 
// 
//
// 输出：0 
//
// 
//
// 解释： 
//
// 
// 1 <= word1.length <= 10⁵ 
// 1 <= word2.length <= 10⁴ 
// word1 和 word2 都只包含小写英文字母。 
// 
//
// Related Topics 哈希表 字符串 滑动窗口 👍 29 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author ldltd
 * @date 2025-01-09 21:50:11
 * @description 3297.统计重新排列后包含另一个字符串的子字符串数目 I
 */
public class CountSubstringsThatCanBeRearrangedToContainAStringI{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 CountSubstringsThatCanBeRearrangedToContainAStringI fun=new CountSubstringsThatCanBeRearrangedToContainAStringI();
	 	 Solution solution = fun.new Solution();
		 System.out.println(solution.validSubstringCount("bbbb", "b"));

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public long validSubstringCount(String word1, String word2) {
		Map<Character, Long> map2 = word2.chars().mapToObj(c -> (char) c).collect(Collectors.groupingBy(c -> c, Collectors.counting()));
		boolean [] checkAr=new boolean[26];
		int check=map2.size();
		int checkCurr=0;
		long res=0;
		Map<Character,Long> map1=new HashMap<>();
		int l=0,r=0;
		int len1 = word1.length();
		int len2 = word2.length();
		while (r<len1||(l<=(len1-len2))){
			if(r<len1){
				map1.put(word1.charAt(r),map1.getOrDefault(word1.charAt(r), Long.valueOf(0))+1);
				if(map2.containsKey(word1.charAt(r))&&map2.get(word1.charAt(r))<=map1.get(word1.charAt(r))&&!checkAr[word1.charAt(r)-'a']){
					checkCurr++;
					checkAr[word1.charAt(r)-'a']=true;
				}
			}else {
				l++;
			}
			if(checkCurr==check){
				while (l<=r&&checkCurr==check){
					map1.put(word1.charAt(l),map1.get(word1.charAt(l))-1);
					res+=(len1-r);
					if(map2.containsKey(word1.charAt(l))&&map2.get(word1.charAt(l))>map1.get(word1.charAt(l))){
						checkCurr--;
						checkAr[word1.charAt(l)-'a']=false;
					}
					l++;
				}
			}
			r++;
		}
		return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
